/*
222. 完全二叉树的节点个数
给出一个完全二叉树，求出该树的节点个数。

思路:
先从根节点出发，向左走，得到树的深度h
然后从根节点的right出发往左走，右子树深度，如果右子树深度===树的深度，左子树满， 2^(h-1)
如果右子树深度<树的深度, 右子树满， 2^(h-2）.
开始递归
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
  if (!root) {
    return 0
  }
  return process(root, 1, getTreeHeight(root, 1))
}

/**
 * 计算位于level层(root为第1层)的node构成的完全二叉树节点个数
 * @param node
 * @param level
 * @param height
 */
function process (node, level, height) {
  if (level === height) {
    return 1 // 已经到了叶子节点了，每个叶子节点构成的完全二叉树节点数为1
  }
  if (height === getTreeHeight(node.right, level + 1)) {
    // 左树满
    return Math.pow(2, height - level) + process(node.right, level + 1, height)
  } else {
    // 右树满
    return Math.pow(2, height - level - 1) + process(node.left, level + 1, height)
  }
}

/**
 * 计算位于level层的node完全二叉树的高度
 * @param node
 * @param level
 */
function getTreeHeight (node, level) {
  while (node) {
    level++
    node = node.left
  }
  return level - 1
}
